跳至主要内容

Increasing Array

題目​

給定一個長度為 nn 的整數陣列，你的目標是要調整這個陣列使得它是遞增的，也就是說陣列中的每一項都大於等於前一項。

每次操作，你可以對陣列中任意一項加一。請問要達到目標至少要做幾次操作？

輸入​

  • 第一行輸入一個整數 nn。（1≤n≤2⋅1051 \le n \le 2 \cdot 10^5）
  • 第二行輸入 nn 個整數 xix_i。（1≤xi≤1091 \le x_i \le 10^9）

輸出​

輸出要達到目標的最少操作次數。

範例測資​

Input:
5
3 2 5 1 7

Output:
5

第二項的 22 加一一次變成 33

第四項的 11 加一四次變成 55

最終的序列會變成

3 3 5 5 7

每一項都大於等於前一項

想法​

假設原本輸入的陣列為 (xi)i=1n(x_i)_{i=1}^n，而操作完的結果陣列為 (yi)i=1n(y_i)_{i=1}^n。

因為每次操作都只能增加數字，所以 yi≥xiy_i \ge x_i。又因為結果陣列要是遞增的，所以 yi≥yi−1y_i \ge y_{i-1}。上面兩個條件綜合起來就是 yi≥max⁡(xi,yi−1)y_i \ge \max(x_i, y_{i-1})，而為了讓操作數最小，我們只要讓結果恰恰好滿足這個條件即可，也就是 yi=max⁡(xi,yi−1)y_i = \max(x_i, y_{i-1})。

因為 yi=max⁡(xi,yi−1)y_i = \max(x_i, y_{i-1})，根據 xix_i 與 yi−1y_{i-1} 的大小關係，有下面兩種情況：

  • xi<yi−1x_i < y_{i-1}：所以 yi=yi−1y_i = y_{i-1}，而這一項的操作數為 yi−xi=yi−1−xiy_i - x_i = y_{i-1} - x_i；
  • xi≥yi−1x_i \ge y_{i-1}：所以 yi=xiy_i = x_i，而這一項的操作數為 yi−xi=0y_i - x_i = 0。

我們可以直接遍歷整個陣列，算出每一項的操作數並加進結果。要求出目前的操作結果 yiy_i，我們不需要記錄整個結果陣列，只需要記錄前一項的操作結果 yi−1y_{i-1} 即可。

注意答案可能會超過 int 範圍。

範例程式碼​

C++ 範例
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long ans = 0;
    int n, pre, x;
    cin >> n;
    cin >> pre;
    for (int i = 1; i < n; i++) {
        cin >> x;
        if (x < pre) {
            ans += pre - x;
        } else {
            pre = x;
        }
    }
    cout << ans;
}